package exercise49;

import java.util.Arrays;

/**
 * @Author Fizz Pu
 * @Date 2021/8/11 下午2:44
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class Lee406 {

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new Lee406().reconstructQueue(
                new int[][]{
                        {7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}
                }
        )));
    }

    public int[][] reconstructQueue(int[][] people) {

        // 按照身高升序排序
        // 身高相同，按照第二个元素降序排序
        Arrays.sort(people,
                (k1, k2) -> {
                    if (k1[0] != k2[0]) {
                        return k1[0] - k2[0];
                    }
                    return k2[1] - k1[1];
                }
        );

        int[][] ret = new int[people.length][];
        int len = ret.length;
        int count;
        for (int[] person: people) {
            count = person[1];
            // 寻找第count + 1个空位
            int tmp = 0;
            int i = 0;
            for (; i < len && tmp <= count; i++) {
                if (ret[i] == null) {
                    tmp++;
                }
            }

            ret[i-1] = person;
        }

        return ret;
    }
}
